#include <stdlib.h>
#include <stdio.h>

// 关键路径算法：仅适用于有向无环图（DAG），核心用于项目管理中的任务调度与工期计算
// 核心逻辑：通过拓扑排序计算事件最早发生时间(ve)，逆拓扑排序计算事件最迟发生时间(vl)，ve==vl的事件构成关键路径

// 1. 基础数据类型定义
typedef char VertexType;  // 顶点数据类型：用字符存储（如'0'、'1'，修复前为int导致格式错乱）
typedef int EdgeType;     // 边的权值类型：表示任务耗时
#define MAXVEX 100        // 图的最大顶点数（可根据需求调整）
#define MAX 0x10000       // 用较大值表示“无穷大”，代表两顶点间无直接边

// 2. 邻接矩阵存储结构（用于初始化图数据，后续转为邻接表便于遍历）
typedef struct {
    VertexType vexs[MAXVEX];          // 顶点表：存储所有顶点
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵：arc[i][j]表示顶点i到j的边权值
    int numVertexes, numEdges;        // 当前图的顶点总数、边总数
} Graph;

// 3. 邻接表存储结构（核心用于拓扑排序和关键路径计算，比邻接矩阵更高效）
// 3.1 边表结点：存储边的目标顶点和权值
typedef struct EdgeNode {
    int edge_vex;            // 该边指向的“目标顶点”在邻接表中的索引（如顶点'3'对应索引3）
    int weight;             // 边的权值（修复前未赋值，导致时间计算错误）
    struct EdgeNode *next;   // 指针：指向当前顶点的下一条边（链表结构）
} EdgeNode;

// 3.2 顶点表结点：存储顶点信息和边表入口
typedef struct VertexNode {
    VertexType data;         // 顶点数据（如'0'、'1'，修复后统一为字符类型）
    int in;                 // 顶点入度（拓扑排序的核心依据：入度为0的顶点优先处理）
    EdgeNode *head;         // 边表入口指针：指向当前顶点的第一条边
} VertexNode;

// 3.3 完整邻接表：由顶点表数组构成
typedef VertexNode AdjList[MAXVEX];
typedef struct {
    AdjList adjList;        // 邻接表主体（顶点表数组）
    int numVertexes, numEdges;        // 顶点总数、边总数（与邻接矩阵保持一致）
} GraphAdjList;
typedef GraphAdjList *Adj_List_Graph;  // 邻接表指针类型（便于函数传参）

// 4. 初始化邻接矩阵图：手动设置顶点数、边数和边权值（项目的任务依赖关系）
void createGraph(Graph *G) {
    // 4.1 固定图的顶点数和边数（根据需求调整，此处为示例数据）
    G->numVertexes = 10;  // 顶点：V0~V9（共10个）
    G->numEdges = 13;     // 边：共13条（对应任务依赖关系）

    // 4.2 初始化顶点表：将索引i转为字符'0'+i（如i=0→'0'，修复前为int导致输出错乱）
    for (int i = 0; i < G->numVertexes; i++) {
        G->vexs[i] = '0' + i;  // 关键修复：顶点数据转为字符类型
    }

    // 4.3 初始化邻接矩阵：对角线为0（自身无环），其余为无穷大（无直接边）
    for (int i = 0; i < G->numVertexes; i++) {
        for (int j = 0; j < G->numVertexes; j++) {
            if (i == j) {
                G->arc[i][j] = 0;  // 自身到自身的边权值为0（无实际意义）
            } else {
                G->arc[i][j] = MAX; // 初始化为无穷大，代表无直接边
            }
        }
    }

    // 4.4 手动设置有向边的权值（项目的任务耗时，对应V0→V1耗时3等）
    G->arc[0][1] = 3;  // V0→V1，耗时3
    G->arc[0][2] = 4;  // V0→V2，耗时4
    G->arc[1][3] = 5;  // V1→V3，耗时5
    G->arc[1][4] = 6;  // V1→V4，耗时6
    G->arc[2][3] = 8;  // V2→V3，耗时8
    G->arc[2][5] = 7;  // V2→V5，耗时7
    G->arc[3][4] = 3;  // V3→V4，耗时3
    G->arc[4][6] = 9;  // V4→V6，耗时9
    G->arc[4][7] = 4;  // V4→V7，耗时4
    G->arc[5][7] = 6;  // V5→V7，耗时6
    G->arc[6][8] = 2;  // V6→V8，耗时2
    G->arc[7][9] = 5;  // V7→V9，耗时5
    G->arc[8][9] = 3;  // V8→V9，耗时3
}

// 5. 将邻接矩阵转为邻接表：为拓扑排序和关键路径计算做准备
// 输入：邻接表指针GL（需初始化）、已创建的邻接矩阵G
void createALGraph(Adj_List_Graph *GL, Graph G) {
    EdgeNode *e;  // 临时边表结点（用于创建新边）

    // 5.1 初始化邻接表：分配内存，复制顶点数和边数
    *GL = (Adj_List_Graph)malloc(sizeof(GraphAdjList));  // 为邻接表分配内存
    (*GL)->numVertexes = G.numVertexes;  // 复制顶点总数
    (*GL)->numEdges = G.numEdges;        // 复制边总数

    // 5.2 初始化邻接表的顶点表：设置顶点数据、入度为0、边表为空
    for (int i = 0; i < G.numVertexes; i++) {
        (*GL)->adjList[i].data = G.vexs[i];  // 顶点数据（如'0'、'1'）
        (*GL)->adjList[i].in = 0;            // 初始入度为0（后续会更新）
        (*GL)->adjList[i].head = NULL;       // 初始边表为空（无任何边）
    }

    // 5.3 构建邻接表的边表：遍历邻接矩阵，将有边的关系转为邻接表的边结点
    for (int i = 0; i < G.numVertexes; i++) {  // 遍历所有“起点”顶点
        for (int j = 0; j < G.numVertexes; j++) {  // 遍历所有“终点”顶点
            // 若邻接矩阵中权值不为0且小于无穷大，说明i到j有直接边
            if (G.arc[i][j] != 0 && G.arc[i][j] < MAX) {
                // 5.3.1 创建新的边表结点，并分配内存
                e = (EdgeNode *)malloc(sizeof(EdgeNode));
                // 5.3.2 设置边结点信息（关键修复：添加weight赋值，之前遗漏导致时间计算错误）
                e->edge_vex = j;                // 边的目标顶点索引（如j=1对应V1）
                e->weight = G.arc[i][j];        // 边的权值（任务耗时，核心修复点）
                e->next = (*GL)->adjList[i].head;  // 新边结点指向当前顶点的第一条边
                (*GL)->adjList[i].head = e;     // 当前顶点的边表入口指向新边结点（头插法）
                (*GL)->adjList[j].in++;         // 目标顶点的入度+1（拓扑排序需用）
            }
        }
    }
}

// 6. 关键路径计算核心函数
// 输入：已构建好的邻接表GL
void critical_path(Adj_List_Graph GL) {
    EdgeNode *e;         // 临时边表结点（用于遍历边）
    int top = -1;        // 拓扑排序辅助栈的栈顶指针（初始为空）
    int top2 = -1;       // 逆拓扑排序辅助栈的栈顶指针（用于计算vl）
    int stack[MAXVEX];   // 拓扑排序辅助栈：存储入度为0的顶点索引
    int stack2[MAXVEX];  // 逆拓扑排序辅助栈：存储拓扑排序后的顶点（逆序用）
    int ve[MAXVEX];      // 事件最早发生时间数组：ve[i]表示顶点i（事件）的最早发生时间
    int vl[MAXVEX];      // 事件最迟发生时间数组：vl[i]表示顶点i（事件）的最迟发生时间
    int curr;            // 当前处理的顶点索引（栈弹出的顶点）
    int k;               // 临时变量：存储边的目标顶点索引

    // 6.1 第一步：拓扑排序并计算事件最早发生时间ve
    // 6.1.1 初始化：将所有入度为0的顶点压入拓扑栈（拓扑排序起点）
    for (int i = 0; i < GL->numVertexes; i++) {
        if (GL->adjList[i].in == 0) {
            stack[++top] = i;  // 栈顶指针+1，再压入顶点索引
        }
    }

    // 6.1.2 初始化ve数组：所有事件最早发生时间初始为0（项目开始时间）
    for (int i = 0; i < GL->numVertexes; i++) {
        ve[i] = 0;
    }

    // 6.1.3 执行拓扑排序：弹出栈顶顶点，更新后续顶点的ve，同时记录逆拓扑顺序（stack2）
    printf("拓扑排序结果：");
    while (top != -1) {  // 栈不为空（还有入度为0的顶点未处理）
        curr = stack[top--];  // 弹出栈顶顶点（当前处理的顶点）
        printf("V%c -> ", GL->adjList[curr].data);  // 输出当前顶点（修复后为V0、V1格式）
        stack2[++top2] = curr;  // 将当前顶点压入逆拓扑栈（后续计算vl用）

        e = GL->adjList[curr].head;  // 指向当前顶点的第一条边
        while (e) {  // 遍历当前顶点的所有出边（即所有后续任务）
            k = e->edge_vex;  // 边的目标顶点索引（后续事件）
            GL->adjList[k].in--;  // 目标顶点的入度-1（处理完一条前驱边）

            // 若目标顶点入度变为0，压入拓扑栈（后续处理）
            if (GL->adjList[k].in == 0) {
                stack[++top] = k;
            }

            // 核心公式：更新事件k的最早发生时间
            // 逻辑：事件k的最早时间 = max(当前ve[k], 事件curr的最早时间 + 边curr→k的耗时)
            if (ve[curr] + e->weight > ve[k]) {
                ve[k] = ve[curr] + e->weight;
            }

            e = e->next;  // 遍历下一条边
        }
    }
    printf("\n");

    // 6.1.4 输出事件最早发生时间ve（验证是否正确，如V9的ve应为27）
    printf("事件最早发生时间(ve)：");
    for (int i = 0; i < GL->numVertexes; i++) {
        printf("V%c:%d -> ", GL->adjList[i].data, ve[i]);
    }
    printf("\n");

    // 6.2 第二步：逆拓扑排序（用stack2）并计算事件最迟发生时间vl
    // 6.2.1 初始化vl数组：所有事件最迟发生时间 = 最后一个事件的最早时间（项目最晚完成时间）
    for (int i = 0; i < GL->numVertexes; i++) {
        vl[i] = ve[GL->numVertexes - 1];  // 最后一个顶点（V9）的ve是项目总工期
    }

    // 6.2.2 执行逆拓扑排序：弹出stack2顶点，更新前驱顶点的vl
    while (top2 != -1) {  // 逆拓扑栈不为空
        curr = stack2[top2--];  // 弹出栈顶顶点（当前处理的顶点，逆拓扑顺序）
        e = GL->adjList[curr].head;  // 指向当前顶点的第一条边
        while (e) {  // 遍历当前顶点的所有出边（找到后续事件k）
            k = e->edge_vex;  // 边的目标顶点索引（后续事件）

            // 核心公式：更新事件curr的最迟发生时间
            // 逻辑：事件curr的最迟时间 = min(当前vl[curr], 事件k的最迟时间 - 边curr→k的耗时)
            if (vl[k] - e->weight < vl[curr]) {
                vl[curr] = vl[k] - e->weight;
            }

            e = e->next;  // 遍历下一条边
        }
    }

    // 6.2.3 输出事件最迟发生时间vl（验证是否正确，如V0的vl应为0）
    printf("事件最迟发生时间(vl)：");
    for (int i = 0; i < GL->numVertexes; i++) {
        printf("V%c:%d -> ", GL->adjList[i].data, vl[i]);
    }
    printf("\n");

    // 6.3 第三步：确定关键路径（ve[i] == vl[i]的顶点构成关键事件）
    // 逻辑：事件的最早和最迟发生时间相等，说明该事件无缓冲时间，是关键节点
    printf("关键路径（关键事件）：");
    for (int i = 0; i < GL->numVertexes; i++) {
        if (ve[i] == vl[i]) {  // 关键事件判定条件
            printf("V%c -> ", GL->adjList[i].data);
        }
    }
    printf("End\n");
    printf("项目总工期：%d\n", ve[GL->numVertexes - 1]);  // 最后一个事件的ve即为总工期
}

// 7. 主函数：程序入口（调用上述函数完成关键路径计算）
int main() {
    Graph G;                // 邻接矩阵图（用于初始化数据）
    Adj_List_Graph GL;      // 邻接表（用于关键路径计算）

    createGraph(&G);        // 步骤1：创建邻接矩阵图（设置顶点、边、权值）
    createALGraph(&GL, G);  // 步骤2：将邻接矩阵转为邻接表（拓扑排序准备）
    printf("关键路径计算结果：\n");
    critical_path(GL);      // 步骤3：计算并输出关键路径

    return 0;  // 程序正常结束
}